{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lexicographically Smallest String After Applying Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLexSmallestString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #执行操作后字典序最小的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 以及两个整数 <code>a</code> 和 <code>b</code> 。其中，字符串 <code>s</code> 的长度为偶数，且仅由数字 <code>0</code> 到 <code>9</code> 组成。</p>\n",
    "\n",
    "<p>你可以在 <code>s</code> 上按任意顺序多次执行下面两个操作之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>累加：将&nbsp; <code>a</code> 加到 <code>s</code> 中所有下标为奇数的元素上（<strong>下标从 0 开始</strong>）。数字一旦超过 <code>9</code> 就会变成 <code>0</code>，如此循环往复。例如，<code>s = \"3456\"</code> 且 <code>a = 5</code>，则执行此操作后 <code>s</code> 变成 <code>\"3951\"</code>。</li>\n",
    "\t<li>轮转：将 <code>s</code> 向右轮转 <code>b</code> 位。例如，<code>s = \"3456\"</code> 且 <code>b = 1</code>，则执行此操作后 <code>s</code> 变成 <code>\"6345\"</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回在 <code>s</code> 上执行上述操作任意次后可以得到的 <strong>字典序最小</strong> 的字符串。</p>\n",
    "\n",
    "<p>如果两个字符串长度相同，那么字符串 <code>a</code> 字典序比字符串 <code>b</code> 小可以这样定义：在 <code>a</code> 和 <code>b</code> 出现不同的第一个位置上，字符串 <code>a</code> 中的字符出现在字母表中的时间早于 <code>b</code> 中的对应字符。例如，<code>\"0158”</code> 字典序比 <code>\"0190\"</code> 小，因为不同的第一个位置是在第三个字符，显然 <code>'5'</code> 出现在 <code>'9'</code> 之前。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"5525\", a = 9, b = 2\n",
    "<strong>输出：</strong>\"2050\"\n",
    "<strong>解释：</strong>执行操作如下：\n",
    "初态：\"5525\"\n",
    "轮转：\"2555\"\n",
    "累加：\"2454\"\n",
    "累加：\"2353\"\n",
    "轮转：\"5323\"\n",
    "累加：\"5222\"\n",
    "累加：\"5121\"\n",
    "轮转：\"2151\"\n",
    "累加：\"2050\"​​​​​\n",
    "无法获得字典序小于 \"2050\" 的字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"74\", a = 5, b = 1\n",
    "<strong>输出：</strong>\"24\"\n",
    "<strong>解释：</strong>执行操作如下：\n",
    "初态：\"74\"\n",
    "轮转：\"47\"\n",
    "累加：\"42\"\n",
    "轮转：\"24\"​​​​​\n",
    "无法获得字典序小于 \"24\" 的字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0011\", a = 4, b = 2\n",
    "<strong>输出：</strong>\"0011\"\n",
    "<strong>解释：</strong>无法获得字典序小于 \"0011\" 的字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>s.length</code> 是偶数</li>\n",
    "\t<li><code>s</code> 仅由数字 <code>0</code> 到 <code>9</code> 组成</li>\n",
    "\t<li><code>1 &lt;= a &lt;= 9</code></li>\n",
    "\t<li><code>1 &lt;= b &lt;= s.length - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lexicographically-smallest-string-after-applying-operations](https://leetcode.cn/problems/lexicographically-smallest-string-after-applying-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lexicographically-smallest-string-after-applying-operations](https://leetcode.cn/problems/lexicographically-smallest-string-after-applying-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"5525\"\\n9\\n2', '\"74\"\\n5\\n1', '\"0011\"\\n4\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        n = len(s)\n",
    "        b = gcd(b, n)\n",
    "        c = int(min(s[::b]))\n",
    "        s = deque(map(int, s))\n",
    "        f = {1: lambda x: x and 10 - x,\n",
    "            2: lambda x: (10 + x % 2 - x) % 10,\n",
    "            5: lambda x: 0 if x < 5 else 5\n",
    "        }[gcd(a, 10)]\n",
    "        m = s.copy()\n",
    "        \n",
    "        def g(j):\n",
    "            if (t := f(s[j])) > 0:\n",
    "                for i in range(j, n, 2):\n",
    "                    s[i] = (s[i] + t) % 10\n",
    "        \n",
    "        for _ in range(n // b):\n",
    "            if b & 1:\n",
    "                g(0)\n",
    "                g(1)\n",
    "            elif s[0] == c:\n",
    "                g(1)\n",
    "            if s < m:\n",
    "                m = s.copy()\n",
    "            s.rotate(b)\n",
    "        return ''.join(map(str, m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        ans = s\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        for _ in range(n):\n",
    "            s = s[-b:] + s[:-b]\n",
    "            for j in range(10):\n",
    "                for k in range(1, n, 2):\n",
    "                    s[k] = str((int(s[k]) + a) % 10)\n",
    "                if b & 1:\n",
    "                    for p in range(10):\n",
    "                        for k in range(0, n, 2):\n",
    "                            s[k] = str((int(s[k]) + a) % 10)\n",
    "                        t = ''.join(s)\n",
    "                        if ans > t:\n",
    "                            ans = t\n",
    "                else:\n",
    "                    t = ''.join(s)\n",
    "                    if ans > t:\n",
    "                        ans = t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        ans = s\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        for _ in range(n):\n",
    "            s = s[-b:] + s[:-b]\n",
    "            for j in range(10):\n",
    "                for k in range(1, n, 2):\n",
    "                    s[k] = str((int(s[k]) + a) % 10)\n",
    "                if b & 1:\n",
    "                    for p in range(10):\n",
    "                        for k in range(0, n, 2):\n",
    "                            s[k] = str((int(s[k]) + a) % 10)\n",
    "                        t = ''.join(s)\n",
    "                        if ans > t:\n",
    "                            ans = t\n",
    "                else:\n",
    "                    t = ''.join(s)\n",
    "                    if ans > t:\n",
    "                        ans = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        def transform_add(s,a,b):\n",
    "            s=list(map(int,s))\n",
    "            for i in range(2):\n",
    "                if b%2==0 and i==0:\n",
    "                    continue\n",
    "                low=10\n",
    "                for j in range(10):\n",
    "                    if(s[i]+j*a)%10<low:\n",
    "                        low=(s[i]+j*a)%10\n",
    "                        op=j\n",
    "                s[i::2]=[(k+op*a)%10 for k in s[i::2]]\n",
    "            return \"\".join(map(str,s))\n",
    "        res='9'*len(s)\n",
    "        idx=0\n",
    "        while 1:\n",
    "            idx=(idx+b)%len(s)\n",
    "            s=s[-b:]+s[:-b]\n",
    "            res=min(res,transform_add(s,a,b))\n",
    "            if idx==0:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        n = len(s)\n",
    "        b = gcd(b, n)\n",
    "        c = int(min(s[::b]))\n",
    "        q = deque(map(int, s))\n",
    "        f = {1: lambda x: x and 10 - x,\n",
    "            2: lambda x: (10 + x % 2 - x) % 10,\n",
    "            5: lambda x: 0 if x < 5 else 5\n",
    "        }.pop(gcd(a, 10))\n",
    "        m = q.copy()\n",
    "        \n",
    "        def g(i):\n",
    "            if (t := f(q[i])) > 0:\n",
    "                for j in range(i, n, 2):\n",
    "                    q[j] = (q[j] + t) % 10\n",
    "        \n",
    "        for _ in range(n // b):\n",
    "            if b & 1:\n",
    "                g(0)\n",
    "                g(1)\n",
    "            elif q[0] == c:\n",
    "                g(1)\n",
    "            if q < m:\n",
    "                m = q.copy()\n",
    "            q.rotate(b)\n",
    "        return ''.join(map(str, m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        n = len(s)\n",
    "        iter2 = n // gcd(n, b)\n",
    "        iter1 = 10 // gcd(10, a)\n",
    "        ans = s\n",
    "        for _ in range(iter2):\n",
    "            s = s[-b:] + s[:-b]\n",
    "            if s < ans:\n",
    "                ans = s\n",
    "            if b % 2 == 0:\n",
    "                for i in range(iter1):\n",
    "                    temp = ''\n",
    "                    for z in range(len(s)):\n",
    "                        if z % 2 == 0:\n",
    "                            temp += s[z]\n",
    "                        else:\n",
    "                            temp += chr(ord('0') + (int(s[z]) + a * i) % 10)              \n",
    "                    if temp < ans:\n",
    "                        ans = temp\n",
    "            else:\n",
    "                for i in range(iter1):\n",
    "                    for j in range(iter1):\n",
    "                        temp = ''\n",
    "                        for z in range(len(s)):\n",
    "                            if z % 2 == 0:\n",
    "                                temp += chr(ord('0') + (int(s[z]) + a * j) % 10)\n",
    "                            else:\n",
    "                                temp += chr(ord('0') + (int(s[z]) + a * i) % 10)              \n",
    "                        if temp < ans:\n",
    "                            ans = temp\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        ans = s\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        for _ in range(n):\n",
    "            s = s[-b:] + s[:-b]\n",
    "            for j in range(10):\n",
    "                for k in range(1, n, 2):\n",
    "                    s[k] = str((int(s[k]) + a) % 10)\n",
    "                if b & 1:\n",
    "                    for p in range(10):\n",
    "                        for k in range(0, n, 2):\n",
    "                            s[k] = str((int(s[k]) + a) % 10)\n",
    "                        t = ''.join(s)\n",
    "                        if ans > t:\n",
    "                            ans = t\n",
    "                else:\n",
    "                    t = ''.join(s)\n",
    "                    if ans > t:\n",
    "                        ans = t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        n = len(s)\n",
    "        res = s \n",
    "        s = list(s)\n",
    "        for _ in range(n):\n",
    "            s = s[-b:] + s[:-b]\n",
    "            for j in range(10):\n",
    "                for k in range(1, n, 2):\n",
    "                    s[k] = str((int(s[k]) + a) % 10)\n",
    "                if b & 1:\n",
    "                    for p in range(10):\n",
    "                        for k in range(0, n, 2):\n",
    "                            s[k] = str((int(s[k]) + a) % 10)\n",
    "                        t = \"\".join(s)\n",
    "                        if res > t:\n",
    "                            res = t\n",
    "                else:\n",
    "                    t = \"\".join(s)\n",
    "                    if res > t:\n",
    "                            res = t\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        ans = s\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        for _ in range(n):\n",
    "            # 对轮转状态进行遍历\n",
    "            s = s[-b:] + s[:-b]\n",
    "\n",
    "            # 累加10次后会回到初始状态\n",
    "            for j in range(10):\n",
    "                for k in range(1, n, 2): s[k] = str((int(s[k]) + a) % 10)          # 1、奇数位累加\n",
    "                \n",
    "                if b & 1:\n",
    "                    for p in range(10):\n",
    "                        for k in range(0, n, 2): s[k] = str((int(s[k]) + a) % 10)  # 2、偶数位累加\n",
    "                        t = ''.join(s)\n",
    "                        if ans > t: ans = t\n",
    "                else:\n",
    "                    t = ''.join(s)\n",
    "                    if ans > t: ans = t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        # 做累加操作的次数和做轮转操作的次数是互相独立的，做轮转的次数并不会影响到能否对偶数位进行累加。因此我们可以先枚举做轮转的次数，然后再枚举做累加的次数，从而找到字典序最小的答案。\n",
    "        result = s\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        for _ in range(n):\n",
    "            s = s[-b:]+ s[:-b] #轮转 b\n",
    "            for j in range(10):\n",
    "                # 奇数位 +a\n",
    "                for k in range(1,n,2):\n",
    "                    s[k] = str((int(s[k])+a)%10)\n",
    "                # 判断b如果是奇数，那么偶数位也可以+a\n",
    "                if b%2==1:\n",
    "                    for p in range(10):\n",
    "                        for q in range(0,n,2):\n",
    "                            s[q] = str((int(s[q])+a)%10)\n",
    "                        t = ''.join(s)\n",
    "                        if result>t:    #注意这里的字典序直接在python里面比就行\n",
    "                            result = t\n",
    "                else:\n",
    "                    t = ''.join(s)\n",
    "                    if result>t:\n",
    "                        result = t\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        s2=list(s)*2 \n",
    "        n=len(s)  \n",
    "        vis=[False]*n  \n",
    "        i=0\n",
    "        ans='9'*n\n",
    "        while not vis[i]:\n",
    "            ocs=s2[i:i+n]\n",
    "           # print(cs)\n",
    "            vis[i]=True \n",
    "            i=(i+b)%n  \n",
    "            for oc in range(10):\n",
    "                up=10 if b%2==1 else 1\n",
    "                for ec in range(up):\n",
    "                    cs=ocs.copy()\n",
    "                    for p in range(1,n,2):\n",
    "                        cs[p]=chr((ord(cs[p])-ord('0')+oc*a)%10+ord('0'))\n",
    "                        cs[p-1]=chr((ord(cs[p-1])-ord('0')+ec*a)%10+ord('0'))\n",
    "                   # print(''.join(cs))\n",
    "                    ans=min(ans,''.join(cs))\n",
    "                    \n",
    "\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        n = len(s)\n",
    "        cur = [int(va) for va in s]     #将字符串转换成数组\n",
    "        ans = cur[:]                    #创建一个新数组\n",
    "\n",
    "        stack = [cur]      //一个新的数组，元素是cur数组\n",
    "        visit = set()           //创建一个集合\n",
    "        visit.add(tuple(cur))      //元素是元组\n",
    "\n",
    "        while stack:        //当队列不为空时\n",
    "            nex = []\n",
    "            for cur in stack:      \n",
    "                if cur < ans: \n",
    "                    ans = cur[:]\n",
    "                move = cur[-b:] + cur[:-b]     //轮转后的数组\n",
    "                if tuple(move) not in visit:\n",
    "                    visit.add(tuple(move))\n",
    "                    nex.append(move)\n",
    "                for i in range(1, n, 2):\n",
    "                    cur[i] = (cur[i] + a) % 10\n",
    "\n",
    "                if tuple(cur) not in visit:\n",
    "                    visit.add(tuple(cur))\n",
    "                    nex.append(cur[:])\n",
    "            stack = nex[:]\n",
    "        return ''.join([str(va) for va in ans])\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque([s])\n",
    "        vis = list(s)\n",
    "        res = s\n",
    "\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            if tmp < res:\n",
    "                res = tmp\n",
    "            t1 = tmp[-b:] + tmp[:-b]\n",
    "            t2 = [int(ch) for ch in tmp]\n",
    "            for i in range(1, len(tmp), 2):\n",
    "                t2[i] = (t2[i] + a) % 10\n",
    "            t2 = ''.join(str(ch) for ch in t2)\n",
    "\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:\n",
    "                    vis.append(t)\n",
    "                    q.append(t)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q, vis = [s], [s]\n",
    "        ans = s\n",
    "        while q:\n",
    "            s = q.pop(0)\n",
    "            if ans > s: ans = s  # 字符串直接比较大小\n",
    "\n",
    "            # 累加（需要转化为数字）\n",
    "            t1 = ''.join([str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)])\n",
    "            # 轮转\n",
    "            t2 = s[-b:] + s[:-b]\n",
    "\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:  # 没见过\n",
    "                    vis.append(t)\n",
    "                    q.append(t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = [s]\n",
    "        vis = {s}\n",
    "        ans = s\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            if ans > cur:\n",
    "                ans = cur\n",
    "            # s1\n",
    "            s1 = ''.join(list(map(str, [(int(c) + a) % 10 if i % 2 == 1 else c for i, c in enumerate(cur)])))\n",
    "            s2 = cur[-b:] + cur[:-b]\n",
    "            if s1 not in vis:\n",
    "                vis.add(s1)\n",
    "                q.append(s1)\n",
    "            if s2 not in vis:\n",
    "                vis.add(s2)\n",
    "                q.append(s2)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        visit=set()\n",
    "        #dfs\n",
    "        #try every case\n",
    "        dfs=[s]\n",
    "        n=len(s)\n",
    "        visit.add(s)\n",
    "        while dfs:\n",
    "            cs=dfs.pop()\n",
    "            #first way\n",
    "            ls=[int(x) for x in cs]\n",
    "            for i in range(1,n,2):\n",
    "                ls[i]=(ls[i]+a)%10\n",
    "            ns=''.join([str(x) for x in ls])\n",
    "            if ns not in visit:\n",
    "                visit.add(ns)\n",
    "                dfs.append(ns)\n",
    "            #second way\n",
    "            ns=cs[b:]+cs[:b]\n",
    "            if ns not in visit:\n",
    "                visit.add(ns)\n",
    "                dfs.append(ns)\n",
    "        small=s\n",
    "        for item in visit:\n",
    "            if item<small:\n",
    "                small=item\n",
    "        return small"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque([s])\n",
    "        vis = {s}\n",
    "        ans = s\n",
    "        while q:\n",
    "            s = q.popleft()\n",
    "            if ans > s:\n",
    "                ans = s\n",
    "            t1 = ''.join([str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)])\n",
    "            t2 = s[-b:] + s[:-b]\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:\n",
    "                    vis.add(t)\n",
    "                    q.append(t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque([s])\n",
    "        vis = {s}\n",
    "        ans = s\n",
    "        while q:\n",
    "            s = q.popleft()\n",
    "            if ans > s:\n",
    "                ans = s\n",
    "            t1 = ''.join([str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)])\n",
    "            t2 = s[-b:] + s[:-b]\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:\n",
    "                    vis.add(t)\n",
    "                    q.append(t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        queue = [s]\n",
    "        ans = s\n",
    "        visit = {s}\n",
    "        while queue:\n",
    "            c = queue.pop(0)\n",
    "            if c < ans:\n",
    "                ans = c\n",
    "            t1_list = []\n",
    "            for i, h in enumerate(c):\n",
    "                if i % 2:\n",
    "                    t1_list.append(str((int(h)+a)%10))\n",
    "                else:\n",
    "                    t1_list.append(h)\n",
    "            t1 = ''.join(t1_list)\n",
    "            t2 = c[-b:] + c[:-b]\n",
    "            for t in (t1, t2):\n",
    "                if t not in visit:\n",
    "                    visit.add(t)\n",
    "                    queue.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        visit=set()\n",
    "        #dfs\n",
    "        #try every case\n",
    "        dfs=[s]\n",
    "        n=len(s)\n",
    "        visit.add(s)\n",
    "        while dfs:\n",
    "            cs=dfs.pop()\n",
    "            #first way\n",
    "            ls=[int(x) for x in cs]\n",
    "            while True:\n",
    "                for i in range(1,n,2):\n",
    "                    ls[i]=(ls[i]+a)%10\n",
    "                ns=''.join([str(x) for x in ls])\n",
    "                if ns not in visit:\n",
    "                    visit.add(ns)\n",
    "                    dfs.append(ns)\n",
    "                else:\n",
    "                    break\n",
    "            #second way\n",
    "            ns=cs[b:]+cs[:b]\n",
    "            if ns not in visit:\n",
    "                visit.add(ns)\n",
    "                dfs.append(ns)\n",
    "        small=s\n",
    "        for item in visit:\n",
    "            if item<small:\n",
    "                small=item\n",
    "        return small"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        def addOp(s, a):\n",
    "            chars = list(s)\n",
    "            for i in range(1, len(chars), 2):\n",
    "                chars[i] = str((int(chars[i]) + a) % 10)\n",
    "            return \"\".join(chars)\n",
    "\n",
    "        def rotateOp(s, b):\n",
    "            return s[-b:] + s[:-b]\n",
    "\n",
    "        visited = set()\n",
    "        queue = [s]\n",
    "        visited.add(s)\n",
    "        res = s  # 初始化为给定的字符串\n",
    "\n",
    "        while queue:\n",
    "            curr = queue.pop(0)\n",
    "            # 更新字典序最小的字符串\n",
    "            res = min(res, curr)\n",
    "\n",
    "            # 尝试累加操作\n",
    "            add_str = addOp(curr, a)\n",
    "            if add_str not in visited:\n",
    "                visited.add(add_str)\n",
    "                queue.append(add_str)\n",
    "\n",
    "            # 尝试轮转操作\n",
    "            rotate_str = rotateOp(curr, b)\n",
    "            if rotate_str not in visited:\n",
    "                visited.add(rotate_str)\n",
    "                queue.append(rotate_str)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque([s])\n",
    "        vis = {s}\n",
    "        ans = s\n",
    "        while q:\n",
    "            s = q.popleft()\n",
    "            if ans > s:\n",
    "                ans = s\n",
    "            t1 = ''.join([str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)])\n",
    "            t2 = s[-b:] + s[:-b]\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:\n",
    "                    vis.add(t)\n",
    "                    q.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque([s])\n",
    "        vis = {s}\n",
    "        ans = s\n",
    "        while q:\n",
    "            s = q.popleft()\n",
    "            if ans > s:\n",
    "                ans = s\n",
    "            t1 = ''.join([str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)])\n",
    "            t2 = s[-b:] + s[:-b]\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:\n",
    "                    vis.add(t)\n",
    "                    q.append(t)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        n = len(s)\n",
    "        cur = [int(va) for va in s]     #将字符串转换成数组\n",
    "        ans = cur[:]                    #创建一个新数组\n",
    "\n",
    "        stack = [cur]      //一个新的数组，元素是cur数组\n",
    "        visit = set()           //创建一个集合\n",
    "        visit.add(tuple(cur))      //元素是元组\n",
    "\n",
    "        while stack:        //当队列不为空时\n",
    "            nex = []\n",
    "            for cur in stack:      \n",
    "                if cur < ans: \n",
    "                    ans = cur[:]\n",
    "                move = cur[-b:] + cur[:-b]     //轮转后的数组\n",
    "                if tuple(move) not in visit:\n",
    "                    visit.add(tuple(move))\n",
    "                    nex.append(move)\n",
    "                for i in range(1, n, 2):\n",
    "                    cur[i] = (cur[i] + a) % 10\n",
    "\n",
    "                if tuple(cur) not in visit:\n",
    "                    visit.add(tuple(cur))\n",
    "                    nex.append(cur[:])\n",
    "            stack = nex[:]\n",
    "        return ''.join([str(va) for va in ans])\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque([s])\n",
    "        vis = set(s)\n",
    "        res = s\n",
    "\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            if tmp < res:\n",
    "                res = tmp\n",
    "            t1 = tmp[-b:] + tmp[:-b]\n",
    "            t2 = [int(ch) for ch in tmp]\n",
    "            for i in range(1, len(tmp), 2):\n",
    "                t2[i] = (t2[i] + a) % 10\n",
    "            t2 = ''.join(str(ch) for ch in t2)\n",
    "\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:\n",
    "                    vis.add(t)\n",
    "                    q.append(t)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque([s])\n",
    "        vis = {s}\n",
    "        ans = s\n",
    "        while q:\n",
    "            s = q.popleft()\n",
    "            if ans > s:\n",
    "                ans = s\n",
    "            t1 = ''.join([str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)])\n",
    "            t2 = s[-b:] + s[:-b]\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:\n",
    "                    vis.add(t)\n",
    "                    q.append(t)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque()\n",
    "        q.append(s)\n",
    "        res = s\n",
    "        visit = {s}\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ns1 = ''\n",
    "            for i in range(len(cur)):\n",
    "                if i % 2 == 1:\n",
    "                    ns1 += str((int(cur[i]) + a) % 10)\n",
    "                else:\n",
    "                    ns1 += cur[i]\n",
    "            if ns1 not in visit:\n",
    "                visit.add(ns1)\n",
    "                res = min(res, ns1)\n",
    "                q.append(ns1)\n",
    "            ns2 = cur[-b:] + cur[:-b]\n",
    "            if ns2 not in visit:\n",
    "                visit.add(ns2)\n",
    "                res = min(res, ns2)\n",
    "                q.append(ns2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        n = len(s)\n",
    "        cur = [int(va) for va in s]     #将字符串转换成数组\n",
    "        ans = cur[:]                    #创建一个新数组\n",
    "\n",
    "        stack = [cur]      //一个新的数组，元素是cur数组\n",
    "        visit = set()           //创建一个集合\n",
    "        visit.add(tuple(cur))      //元素是元组\n",
    "\n",
    "        while stack:        //当队列不为空时\n",
    "            nex = []\n",
    "            for cur in stack:      \n",
    "                if cur < ans: \n",
    "                    ans = cur[:]\n",
    "                move = cur[-b:] + cur[:-b]     //轮转后的数组\n",
    "                if tuple(move) not in visit:\n",
    "                    visit.add(tuple(move))\n",
    "                    nex.append(move)\n",
    "                for i in range(1, n, 2):\n",
    "                    cur[i] = (cur[i] + a) % 10\n",
    "\n",
    "                if tuple(cur) not in visit:\n",
    "                    visit.add(tuple(cur))\n",
    "                    nex.append(cur[:])\n",
    "            stack = nex[:]\n",
    "        return ''.join([str(va) for va in ans])\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        q = deque([s])\n",
    "        vis = set(s)\n",
    "        res = s\n",
    "\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            if tmp < res:\n",
    "                res = tmp\n",
    "            t1 = tmp[-b:] + tmp[:-b]\n",
    "            t2 = [int(ch) for ch in tmp]\n",
    "            for i in range(1, len(tmp), 2):\n",
    "                t2[i] = (t2[i] + a) % 10\n",
    "            t2 = ''.join(str(ch) for ch in t2)\n",
    "\n",
    "            for t in (t1, t2):\n",
    "                if t not in vis:\n",
    "                    vis.add(t)\n",
    "                    q.append(t)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\tdef findLexSmallestString(self, s: str, a: int, b: int) -> str:\r\n",
    "\t\t'''list stack recursion'''\r\n",
    "\t\t# Define Two Functions\r\n",
    "\t\t# Add Operation\r\n",
    "\t\tdef add(string):\r\n",
    "\t\t\tret = []\r\n",
    "\t\t\tfor i, c in enumerate(string):\r\n",
    "\t\t\t\tif i % 2:\r\n",
    "\t\t\t\t\tret.append(str((int(c) + a) % 10))\r\n",
    "\t\t\t\telse:\r\n",
    "\t\t\t\t\tret.append(c)\r\n",
    "\t\t\treturn \"\".join(ret)\r\n",
    "\r\n",
    "\t\t# Rotate Operation using nagetive slice\r\n",
    "\t\trotate = lambda string: string[-b:] + string[:-b]\r\n",
    "\r\n",
    "\t\tres = set()\r\n",
    "\t\tstack = [s]\r\n",
    "\t\twhile stack: \r\n",
    "\t\t\tcur = stack.pop() # current string\r\n",
    "\t\t\tres.add(cur) # add to res set\r\n",
    "\t\t\t# add and rotate separately\r\n",
    "\t\t\tfor val in [add(cur), rotate(cur)]:\r\n",
    "\t\t\t\tif val not in res:\r\n",
    "\t\t\t\t\tstack.append(val)\r\n",
    "\r\n",
    "\t\treturn min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        visit=set()\n",
    "        #dfs\n",
    "        #try every case\n",
    "        dfs=[s]\n",
    "        n=len(s)\n",
    "        visit.add(s)\n",
    "        adds=set()\n",
    "        move=set()\n",
    "        while dfs:\n",
    "            cs=dfs.pop()\n",
    "            #first way\n",
    "            csa=cs\n",
    "            ls=[int(x) for x in cs]\n",
    "            while csa not in adds:\n",
    "                adds.add(csa)\n",
    "                for i in range(1,n,2):\n",
    "                    ls[i]=(ls[i]+a)%10\n",
    "                csa=''.join([str(x) for x in ls])\n",
    "                if csa not in visit:\n",
    "                    visit.add(csa)\n",
    "                    dfs.append(csa)\n",
    "            #second way\n",
    "            csb=cs\n",
    "            while csb not in move:\n",
    "                move.add(csb)\n",
    "                csb=csb[b:]+csb[:b]\n",
    "                if csb not in visit:\n",
    "                    visit.add(csb)\n",
    "                    dfs.append(csb)\n",
    "        small=s\n",
    "        for item in visit:\n",
    "            if item<small:\n",
    "                small=item\n",
    "        return small"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n",
    "        n = len(s)\n",
    "        cur = [int(va) for va in s]\n",
    "        ans = cur[:]\n",
    "\n",
    "        stack = [cur]\n",
    "        visit = set()\n",
    "        visit.add(tuple(cur))\n",
    "\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for cur in stack:\n",
    "                if cur < ans:\n",
    "                    ans = cur[:]\n",
    "                move = cur[-b:] + cur[:-b]\n",
    "                if tuple(move) not in visit:\n",
    "                    visit.add(tuple(move))\n",
    "                    nex.append(move)\n",
    "                for i in range(1, n, 2):\n",
    "                    cur[i] = (cur[i] + a) % 10\n",
    "\n",
    "                if tuple(cur) not in visit:\n",
    "                    visit.add(tuple(cur))\n",
    "                    nex.append(cur[:])\n",
    "            stack = nex[:]\n",
    "        return ''.join([str(va) for va in ans])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
